package com.xzz.dp;

/**
 * @author: hhz
 * @create: 2022-02-17 13:43
 * 688. 骑士在棋盘上的概率
 **/
public class KnightProbability {
    public static void main(String[] args) {
        System.out.println(knightProbability(3,2,0,0));
    }
    public static double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};
        double[][][] dp = new double[n][n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][0] = 1;
            }
        }
        for (int p = 1; p <= k; p++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] d : dirs) {
                        int nx = i + d[0], ny = j + d[1];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                        dp[i][j][p] += dp[nx][ny][p - 1] / 8;
                    }
                }
            }
        }
        return dp[row][column][k];
    }
}
